When a change occurs about nodes, paths between nodes and the laying situation (topology) of the network link in the network, data may go through a point through which cannot be gone before the change, or data may not go through a point through which can be gone before the change.
When it is necessary to always know a shortest path from a starting node to a terminating node, with a change of the topology of the path, it is necessary to calculate again the shortest path from the starting node to the terminating node in the topology after the change.
The conventional shortest path calculating apparatus is configured to calculate again each shortest path between a node pair by using topology information representing topology after the change. In “A Note on Two Problems in Connexion with Graphs” (E. W. Dijkstra, Jun. 11, 1959, Numerische Mathematik 1, p269-271), a method to calculate again each shortest path between a node pair by using topology information is mentioned.
When a shortest path between a predetermined node pair is already calculated, there is a case that there is a common part (called “common part” as follows) between this calculated shortest path between a node pair and shortest path between other node pair which is to be calculated.
When there is the common part, this common part can be used as a part of the calculation result for calculation of the shortest path between the node pair which is to be calculated.
In particular, when a part representing shortest path between the node pair from starting point to terminating point which is to be calculated (called “part path” as follows) is included in the calculated shortest path between the node pair, this part path is equal to shortest path between the node pair which is calculated.
If a group of shortest paths consisting of each calculated shortest path between the pair of nodes includes a lot of part paths, calculation time of each shortest path between the node pair which is to be calculated is shortened by use of this calculated group of shortest paths.
Conventionally, there is no technology to shorten calculation time of each shortest path between the node pair by paying attention to this point (If a group of shortest paths consisting of each calculated shortest path between the node pair includes a lot of part paths, calculation time of each shortest path between the node pair which is to be calculated is shortened by use of this calculated group of shortest paths.).
A purpose of the present invention is to provide a path calculation order deciding method, a program and a calculating apparatus which decide calculation order of the shortest path between the node pair in order to shorten calculation time of shortest path between other node pair by use of each calculated shortest path between the node pair.
According to the present invention, in a decreasing order of the numbers of the paths which can be just used when each shortest path between other node pair is calculated, each shortest path between other node pair can be calculated. Therefore, calculation time of each shortest path between other node pair can be shortened.
The present invention is a path calculation order determining method that is executed by a calculating apparatus, to calculate a shortest path between other node pair by use of information of calculated shortest paths between node pairs in a network including a plurality of nodes, the method including: a step of storing calculated shortest path group information about calculated shortest paths which are calculated shortest paths starting from an identical node and terminating at nodes other than the starting node, and also storing topology information on topology of the plurality of nodes in the network, in a memory medium included in the calculating apparatus; and a calculation step of calculating a shortest path between a node pair, which has, as its starting node, a node other than the starting node of the calculated shortest paths and having the most nodes located downstream therefrom on the calculated shortest paths, and has, as its terminating node, each node of the plurality of nodes other than its starting node, by use of the calculated shortest path group information and the topology information.
The present invention is a system that includes a processor and a non-transitory computer readable medium for storing program instructions, calculated shortest path group information on calculated shortest path groups each of which includes shortest paths starting from an identical starting node and terminating at nodes other than the starting node, and topology information on topology of nodes in a network including a plurality of nodes. The instructions include a calculation step of calculating a shortest path between a node pair, which has, as its starting node a node other than the starting node of the calculated shortest paths and has the most nodes located downstream therefrom on the calculated shortest paths, and has, as its terminating node, each node of the plurality of nodes other than its starting node, by use of the calculated shortest path group information and the topology information.
The present invention is also a calculating apparatus for determining a path calculation order to calculate a shortest path between a node pair by use of calculated shortest paths in a network including a plurality of nodes. The apparatus includes: a memory medium storing calculated shortest path group information on calculated shortest path groups each of which includes shortest paths starting from an identical node and terminating at nodes other than the starting node, and also storing topology information on topology of the plurality of nodes in the network; and a calculation unit executing a calculation step of calculating a shortest path between a node pair, which has, as its starting node, a node other than the starting node of the calculated shortest paths and has the most nodes located downstream therefrom on the calculated shortest paths, and has, as its terminating node, each node of the plurality of nodes other than its starting node, by use of the calculated shortest path group information and the topology information.
In addition, it is preferable that the calculation step includes steps executed by the calculating apparatus of: a search step of searching every node located one-hop downstream from the starting node on the paths included in the calculated shortest path group as calculation starting nodes; a selection step of selecting a node as a particular calculation starting node having the most nodes that are located downstream therefrom among; the calculation starting nodes a shortest path calculation step of calculating a shortest path starting from the particular calculation starting node and terminating at each of nodes other than the particular calculation starting node by use of the calculated shortest path group information for nodes on a path that are included in the calculated shortest path group, or the topology information for nodes on paths that are not included in the calculated shortest path group; and a repetition step of adding the searched node by the searched step as the calculation starting node, and repeating the search step, the selection step and the shortest path calculation step, until the calculation of every shortest path starting from each of the calculation starting nodes is over.